Beim externen Rechnen geht es um die Lösung komplexer Probleme: Probleme, die so komplex sind, da;ß die anfallenden Datenmengen nicht in den Hauptspeicher passen und ausgelagert werden müssen.

Die traditionellen Methoden, Algorithmen asymptotisch zu analysieren, reichen für dieses Gebiet bei weitem nicht aus. Traditionell wird angenommen, da;ß alle Daten in den Hauptspeicher passen, so da;ß elementare Operationen in konstanter Zeit ausgeführt werden können. Methoden zum externen Rechnen versuchen, den Aufwand zum Ein- und Auslagern der anfallenden grossen Datenmengen zu berücksichtigen. Bisherige Ansätze reichen aber zur Beurteilung der praktischen Verwendbarkeit nicht aus. Es werden nicht nur sämtliche Konstanten vernachlässigt, vor allem aber wird auch mit weitgehend vereinfachten Modellen gearbeitet, z.B. wird meistens angenommen, da;ß beliebige interne Operationen nun umsonst durchgeführt werden können.

Unser Ziel ist es, zur Behebung dieser Mankos beizutragen. In einer ersten Arbeit haben wir versucht, Ansätze für paralleles Rechnen auch für externes Rechnen nutzbar zu machen.

Veröffentlichung:

Sibeyn, J.F., M. Kaufmann, `BSP-Like External-Memory Computation,' Proc. 3rd Italian Conference on Algorithms and Complexity, LNCS 1203, pp. 229-240, 1997.